package main

import "go-leetcode/leetcode/utils"

func main() {

}

func getValidPaths(root *utils.TreeNode, targetSum int) [][]int {
	var res [][]int

	var treeNodes []int

	var dfsPath func(node *utils.TreeNode, sum int)
	dfsPath = func(node *utils.TreeNode, sum int) {
		if node == nil {
			return
		}

		if node.Left == nil && node.Right == nil {
			// 已经到叶子节点，判定是否符合条件
			if node.Val == sum {
				treeNodes = append(treeNodes, node.Val)
				res = append(res, append([]int{}, treeNodes...))
				treeNodes = treeNodes[:len(treeNodes)-1]
			}
		}

		treeNodes = append(treeNodes, node.Val)
		dfsPath(node.Left, sum-node.Val)
		dfsPath(node.Right, sum-node.Val)
		treeNodes = treeNodes[:len(treeNodes)-1]
	}

	dfsPath(root, targetSum)

	return res
}
